\section{Metodologia}
\label{metodologia}

% Definição do estudo de caso

% Primeira fase: Análise de estratégias e parâmetros

% Segunda fase: Análise de condições de parada

Nesta seção é descrita a abordagem adotada para a análise de estratégias para solucionar o PVC utilizando AG. Um estudo de caso é definido para que a avaliação das soluções seja realizada. O processo de análise está dividido em duas fases: na primeira, estratégias de AG e os diferentes parâmetros envolvidos são avaliados; na segunda fase, a estratégia com melhor desempenho na primeira fase é usada para análise de diferentes métodos de condição de parada.

\subsection{Definição do estudo de caso}

Como objeto de estudo, utilizou-se o PVC para um conjunto de oito cidades. A distância entre duas cidades é simétrica, ou seja, dadas duas cidades $A$ e $B$, a distância de $A$ para $B$ é igual à distância de $B$ para $A$. As distâncias entre as cidades são descritas na Tabela \ref{tabela:cidades}.

\begin{table*}[ht]
  \caption{Distância entre as cidades}
  \label{tabela:cidades}
  \centering
  \small
  \begin{tabular}{|c||c|c|c|c|c|c|c|c|}
		\hline
		Cidades/Cidades & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline\hline
		1 & 0 & 42 & 61 & 30 & 17 & 82 & 31 & 11 \\ \hline
		2 & 42 & 0 & 14 & 87 & 28 & 70 & 19 & 33 \\ \hline
		3 & 61 & 14 & 0 & 20 & 81 & 21 & 8 & 29 \\ \hline
		4 & 30 & 87 & 20 & 0 & 34 & 33 & 91 & 10 \\ \hline
		5 & 17 & 28 & 81 & 34 & 0 & 41 & 34 & 82 \\ \hline
		6 & 82 & 70 & 21 & 33 & 41 & 0 & 19 & 32 \\ \hline
		7 & 31 & 19 & 8 & 91 & 34 & 19 & 0 & 59 \\ \hline
		8 & 11 & 33 & 29 & 10 & 82 & 32 & 59 & 0 \\ \hline
  \end{tabular}
\end{table*}

\subsection{Primeira fase}

Para escolher a melhor estratégia para o estudo de caso, serão executados experimentos com as estratégias identificadas na literatura, fazendo uma varredura de parâmetros do AG para uma posterior avaliação de desempenho de cada solução.

A escolha das estratégias e parâmetros usados nos experimentos foi feita através de um levantamento bibliográfico do estado da arte. A Tabela \ref{tabela:parametros} apresenta os parâmetros seus valores utilizados na varredura de parâmetros.

\begin{table*}[ht]
  \caption{Valores para a varredura de parâmetros}
  \label{tabela:parametros}
  \centering
  \small
 \begin{tabular}{|c|c|}
	\hline
	\textbf{Parâmetro} & \textbf{Valores} \\
	\hline
	Seletor natural & Melhor \textit{fitness}, Roleta, Torneio \\
	Elitismo & Sim, Não \\
	Cromossomos duplicados & Sim, Não \\
	Representação do cromossomo & Cadeia de inteiros \\
	Geração da população inicial & Aleatória, Igual \\
	Tamanho da população inicial & $512$ \\
	Estratégia de cruzamento & Heurística (guloso 1) \\
	Estratégia de mutação & Troca gulosa \\
	Taxa de mutação & $5\%$ \\
	Tamanho do torneio & $1,3,5,7,10$ \\
	Taxa de seleção do melhor indivíduo & $0.7, 0.8, 0.9, 1$ \\
	\hline
\end{tabular}
\end{table*}

Para evitar uma explosão na quantidade de experimentos, alguns parâmetros foram
fixados em apenas um valor possível na varredura de parâmetros. Alguns desses
valores foram derivados de resultados presentes literatura. É o caso da representação do cromossomo através
de cadeia de inteiros, da estratégia de cruzamento heurística e da estratégia de
mutação com troca gulosa, descritos na Seção \ref{estado_da_arte}. A taxa de
mutação e tamanho inicial da população também foram fixados, utilizando-se
valores comumente usados. Os outros parâmetros foram variados com faixas de
valores que tentam cobrir as possíveis boas soluções.

A métrica utilizada para comparar os diferentes cenários e experimentos foi identificar a partir de qual geração todas as soluções geradas convergiam para a solução ótima. Assim, a melhor solução seria aquela que alcançasse essa convergência com o menor número de gerações. Caso haja empate nos resultados da primeira métrica, uma segunda métrica de tempo de convergência para a solução ótima é usada. Quanto menor o tempo de convergência, melhor a solução.

\subsection{Segunda fase}

Para a segunda fase de experimentações, a melhor solução identificada na primeira fase é usada para a análise de estratégias de condição de parada. Duas estratégias foram escolhidas para a avaliação. Na primeira, um limite no número máximo de gerações é estabelecido. Na segunda, é estabelecido um limite no número máximo de gerações sem que haja alteração no melhor \textit{fitness}. Foi adotada uma condição de parada híbrida que utiliza essas duas estratégias. A análise consiste em encontrar valores adequados para os limites das duas estratégias. Como o AG é não-determinístico, as decisões tomadas serão probabilísticas e irão depender da confiabilidade escolhida. Para tomar tal decisão, serão construídas através dos resultados dos experimentos a função densidade de probabilidade (FDP) para o número de gerações necessárias para convergir para a solução ótima e a FDP para o número máximo de repetições do melhor \textit{fitness} até encontrar a solução ótima. Os valores para as condições de parada serão obtidos usando o $X$-quantil, onde $X$ é a probabilidade para que a melhor solução seja obtida.